package com.company.class10;

import java.util.Arrays;

/**
 * @Classname HomeWork
 * @Description 类型说明
 * @Date 2022/5/3 0:20
 * @Created by zbw
 */

public class HomeWork {
    public static void main(String[] args) {
        int[] a = {2,1,4,6,3,5,9,8,7,3,2};
        System.out.println("排序前："+Arrays.toString(a));
        quickSort(a,0,a.length-1);
        System.out.println("排序后："+Arrays.toString(a));

    }
    public static void quickSort(int[] a,int start,int end){
        //定义基准、左右下标
        int base = a[end];
        int left =start;
        int right = end;
        //循环结束为left=right
        while(left < right){
            //从左往右的遍历
            while (left < right){
                //如果left值比基准值小，不用动，left++
                if(a[left] < base){
                    left++;
                }else {
                    //如果比基准值大，交换 left和right（基准值）的位置，切换到从右往左进行遍历，rigth--
                    a[right] = a[left];
                    a[left] = base;
                    right--;
                    break;
                }

            }
            //从右往左的遍历
            while (left < right){
                //如果right值比基准值大，不用动，right--
                if(a[right] > base){
                    right--;
                }else {
                    //如果比基准值小，交换 left(基准值)和right的位置，切换到从左往右进行遍历，left++
                    a[left] = a[right];
                    a[right] = base;
                    left++;
                    break;
                }

            }
        }
        //递归操作
        //排完之后，判断是否接着排序：
        //左边的条件：left - start <= 1
        if(left - start > 1){
            quickSort(a,start,left-1);
        }
        //右边的条件：end - left <= 1
        if(end - left > 1){
            quickSort(a,left+1,end);
        }

    }
}
